/**
 * Basic logic for the traversal and search within a Graph object.
 */
GraphApp.Traverse = (function () {
  var Queue, Stack, Traverser;
	
  /**
   * Implementation of a basic Queue.
   * @constructor
   * @private
   */
  Queue = function () {
    this.memory = [];
  };
	
  Queue.prototype = {
    /**
     * Inserts the specified element into this queue.
     * @param {Object} elem The element to insert.
     */
    push : function (elem) {
      this.memory.push(elem);
    },
		
    /**
     * Retrieves and removes the head of this queue.
     */
    pop : function () {
      return this.memory.shift();
    },
		
    /**
     * Checks if this queue is empty.
     * @returns {Boolean} True if the queue is empty, false otherwise.
     */
    isEmpty : function () {
      return this.memory.length === 0;
    }
  };
  
  /**
   * Implementation of a basic Stack.
   * @constructor
   * @private
   */
  Stack = function () {
    this.memory = [];
  };
  
  Stack.prototype = {
    /**
     * Inserts the specified element into this stack.
     * @param {Object} elem The element to insert.
     */
    push : function (elem) {
      this.memory.push(elem);
    },

    /**
     * Retrieves and removes the head of this stack.
     */
    pop : function () {
      return this.memory.pop();
    },

    /**
     * Checks if this stack is empty.
     * @returns {Boolean} True if the stack is empty, false otherwise.
     */
    isEmpty : function () {
      return this.memory.length === 0;
    }
  };
  
  /**
   * Object which allows to search within a graph for a specified value.
   * The type of the algorithm which should be used to traverse the graph
   * can be specified.
   * @param {Graph} graph The Graph object for which this Traverser is used.
   */
  Traverser = function (graph) {
    // The Graph object.
    this.graph = graph;
    // Stores the ids of the already visited nodes during the traversion.
    this.marked = {};
    // Stores the currently selected node.
    this.current = {};
    // Dummy variable used to decide which action should be executed next.
    this.state = 0;
    // The search string which should be found within the graph.
    this.searchValue = '';
    // The algorithm which should be used for the traversial (BFS | DFS)
    this.algorithm = '';
    // The memory structure of the Traverser (depends on the used algorithm)
    this.memory = {};
    // The starting node of the search.
    this.startingPoint = {};
  };
	
  Traverser.prototype = {
    /**
     * Executes a traversal with the specified properties.
     * @returns {Array} An array which contains the nodes in the order in 
     * which the traversal algorithm visited them.
     */
    traverse : function() {
      var running = true;
      var result = [];
      while(running) {
        var stepresult = this.step();
        if (stepresult[0] === true) {
          result = result.concat(stepresult[1]);
          running = false;
        } else if (stepresult === false) {
          running = false;
        } else {
          result = result.concat(stepresult);
        }
      }
      return result;
    },
    
    /** 
     * Executes a single step of the traversial algorithm.
     * @returns {Node|Boolean|Array} During the traversial algorithm each call
     * of the step function returns the Node object which has been visited 
     * during this step or an empty Array if no node has been visited. If
     * the search value is found the function returns an Array which contains
     * true on its 0 index and the Node on index 1. If there are no further
     * nodes in the graph and the search value has not been found, 
     * or if any of the necessary property values is not set, the step 
     * function returns false.
     * 
     * returns false if value not found or value or starting point not defined
     * returns true if value is found
     */    
    step : function() {
      if (this.searchValue === '' || (this.memory.isEmpty() && this.state === 0)) {
        return false;
      }
      
      if (this.state === 0) {
        this.current = this.memory.pop();
        if (this.current.value == this.searchValue) {
          return [true, this.current];
        } else {
          this.state = 1;
          return [this.current];
        }
      } else if (this.state === 1) {
        var children = this.graph.neighbors(this.current.id);
        var addmarks = []
        for (var key in children) {
          var node = this.graph.nodes[children[key]];
          if (!this._isMarked(node.id)) {
            addmarks.push(node);
            this._mark(node.id);
            this.memory.push(node);
          }
        }
        this.state = 0;		
        return [];
      }
    },
    
    /**
     * Define the algorithm which should be used for the traversion.
     * @param {String} algorithm Specifies the algorithm Breadth-First-Search
     * (BFS) or Depth-First-Search (DFS) which should be used.
     */
    setAlgorithm : function(algorithm) {
      if (algorithm === "BFS") {
        this.algorithm = "BFS";
      } else {
        this.algorithm = "DFS";
      }
      this.setStartingPoint(this.startingPoint); 
    },

    /**
     * Sets the starting node of the traversion.
     * @param {Node} node The node from which the traversion should start.
     */
    setStartingPoint : function(node) {
      this.startingPoint = node;
      if (this.algorithm === "BFS") {
        this.memory = new Queue();      
      } else {
        this.memory = new Stack();
      }
      this.memory.push(node);
    },

    /**
     * Sets the search value.
     * @param {String} value The search value.
     */
    setSearchValue : function(value) {
      this.searchValue = value;
    },

    /**
     * Checks if the node with the specified id has been marked by the
     * algorithm as a node of future inspectation.
     * @private
     * @param {Integer} id The identifier of the node which should be checked.
     */
    _isMarked : function(id) {
      return this.marked[id];
    },

    /**
     * Marks a node with the specified id for future inspectation.
     * @private
     * @param {Integer} id The identifier of the node to mark.
     */
    _mark : function(id) {
      this.marked[id] = true;
    }
  };	

  return {
    Traverser: Traverser
  };
}());
